package ljl.alg.wangzheng_camp.round1.bitwise;

import java.util.BitSet;

public class _offer56_2_single_number {
    
    /**
     * 这个去 jianzhioffer 包里找吧，那里有详细解释
     * */
    public int singleNumber(int[] nums) {
        int ones = 0, twos = 0;
        for (int num : nums) {
            ones = (ones ^ num) & ~twos;
            twos = (twos ^ num) & ~ones;
        }
        return ones;
    }
    
    public int singleNumber2(int[] nums) {
        int[] count = new int[32];
        for (int num : nums) {
            for (int i = 0; i < 32; i++) {
                count[i] += num & 1;
                num >>= 1;
            }
        }
        int res = 0;
        for (int i = 0; i < 32; i++) {
            res <<= 1;
            res |= count[31 - i] % 3;
        }
        return res;
    }
    
    public int singleNumber3(int[] nums) {
        int[] bits = new int[32];
        for (int num : nums) {
            for (int i = 0; i < 32; i++) {
                if ((num & 1) == 1) {
                    bits[i]++;
                }
                num >>= 1;
            }
        }
        int mask = 1;
        int res = 0;
        for (int i = 0; i < 32; i++) {
            if ((bits[i] % 3 != 0)) {
                res |= mask;
            }
            mask <<= 1;
        }
        return res;
    }
    
    /**
     * 总能想到非常慢的点子！
     *
     * 你这个蠢办法还不如数组聪明
     *
     * */
    public int singleNumber4(int[] nums) {
        BitSet one = new BitSet(32), two = new BitSet(32);
        for (int num : nums) {
            for (int i = 0; i < 32; i++) {
                if ((num & 1) == 1) {
                    if (one.get(i)) {
                        two.set(i);
                        one.clear(i);
                    } else {
                        if (two.get(i)) {
                            one.clear(i);
                            two.clear(i);
                        } else {
                            one.set(i);
                        }
                    }
                }
                num >>= 1;
            }
        }
        int res = 0;
        int mask = 1;
        for (int i = 0; i < 32; i++) {
            if (one.get(i)) res |= mask;
            mask <<= 1;
        }
        return res;
    }
    
}
